package com.jsy.common.leetcode;

import java.util.HashMap;
import java.util.Map;

public class MergeArray {
    public static void main(String[] args) {
//        Solution1.merge(new int[]{1,2,3,0,0,0},3,new int[]{4,5,6},3);
//        Solution1.merge(new int[]{1,2,3,0,0,0},3,new int[]{3,5,6},3);
//        Solution1.merge(new int[]{1,0},1,new int[]{2},1);
//        Solution1.merge(new int[]{2,0},1,new int[]{1},1);
//        int i = removeElement(new int[]{2, 1, 3, 1}, 1);
//        int i = removeDuplicates2(new int[]{1, 1,1, 2, 3});
//        rotate(new int[]{1,2,3,4,5,6,7}, 3);
//        rotate(new int[]{-1}, 2);
          System.out.println(maxProfit(new int[]{7,6,4,3,5}));
//        System.out.println(i);
    }

    public static int removeElement(int[] nums, int val) {
        int count = 0;
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val){
                result[count++] = nums[i];
            }
        }
        for (int i = 0; i < result.length; i++) {
            nums[i] = result[i];
        }
        return count;
    }

    public static int removeDuplicates(int[] nums) {
        int[] result = new int[nums.length];
        int count = 0;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(String.valueOf(nums[i])) == null){
                map.put(String.valueOf(nums[i]),1);
                result[count++] = nums[i];
            }
        }
        for (int i = 0; i < result.length; i++) {
            nums[i] = result[i];
        }
        return count;
    }

    public static int removeDuplicates2(int[] nums) {
        int p = 1;
        int q = 1;
        int count = 0;
        for (;q < nums.length; q++) {
            if (nums[q] != nums[q-1]){
                count = 0;
                nums[p++] = nums[q];
            } else {
                count++;
            }
            if (count == 1 ){
                nums[p++] = nums[q];
            }
        }
        return p;
    }


    public int majorityElement(int[] nums) {
        if (nums.length == 0){
            return 0;
        }
        int result = 0;
        Map<Integer, Integer> elementMap = new HashMap<>();
        for (int num : nums) {
            Integer integer = elementMap.get(num);
            if (integer!=null){
                elementMap.put(num,integer+1);
            }else {
                elementMap.put(num,1);
            }
        }
        int max = 0;
        for (Map.Entry<Integer, Integer> entry : elementMap.entrySet()) {
            Integer value = entry.getValue();
            if (max < value){
                max = value;
                result = entry.getKey();
            }
        }
        return result;
    }
    public static void rotate(int[] nums, int k) {
        if(nums.length == 0){
            return;
        }
        //移动位置取模
        k = k%nums.length;
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int index = i-k;
            if (index >= nums.length){
                index = index-nums.length;
            }
            if (index < 0){
                index += nums.length;
            }
            result[i] = nums[index];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = result[i];
            System.out.println(nums[i]);
        }
    }
//差值
    public static int maxProfit(int[] prices) {
        if (prices.length <=1){
            return 0;
        }
        int maxProfit = 0;
        int miniPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i]< miniPrice){
                miniPrice = prices[i];
            }else if (prices[i] - miniPrice > maxProfit){
                maxProfit = prices[i] - miniPrice;
            }
        }
        return maxProfit;
    }
}
class Solution1 {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int [] merge = new int[m+n];
        int i = 0;
        int j = 0;
        if( m == 0 || n == 0){
           if (n > 0){
               for (int k = 0; k < n; k++) {
                   nums1[k] = nums2[k];
               }
           }
           return;
        }
        boolean flag = false;
        int tempMax = nums1[m-1];
        while (true){
            if (i == m-1){
                if (tempMax > nums2[j]){
                    merge[i+j] = nums2[j];
                }else {
                    merge[i+j] = tempMax;
                    tempMax = nums2[j];
                }
                if (j < n-1){
                    j++;
                }
                flag = true;
                if(i+j+1 >= m+n-1){
                    if (tempMax > nums2[j]){
                        merge[i+j] = nums2[j];
                        merge[i+j+1] = tempMax;
                    }else {
                        if (tempMax == nums1[i]){
                            merge[i+j] = tempMax;
                        }else {
                            if (j-1>0){
                                merge[i+j] = nums2[j-1];
                            }
                        }
                        merge[i+j+1] = nums2[j];
                    }
                    break;
                }
            }
            if (!flag){
                if (nums1[i] > nums2[j]){
                    merge[i+j] = nums2[j];
                    if (j < n-1){
                        j++;
                    }
                } else {
                    merge[i+j] = nums1[i];
                    if (i < m-1){
                        i++;
                    }
                }
            }
        }
        for (int z = 0; z < nums1.length; z++) {
            nums1[z] = merge[z];
            System.out.println(nums1[z]);
        }
    }
}
